---
sidebar_position: 5
---

# 5. Контейнер map

## Основные сведения

Шаблонный класс map входит в библиотеку STL. Вскоре вы убедитесь, что можно очень много сделать, если знать основные принципы работы класса map, не разбираясь в его реализации.

Ассоциативные контейнеры (отображения), хранящие данные в отсортированном виде, сродни словарю. В результате вставка в них осуществляется медленнее, чем в последовательные контейнеры, но, когда дело доходит до поиска, преимущества ассоциативных контейнеров оказываются существенными.

Отображение хранит пары “ключ-значение” с уникальными ключами, отсортированными по значениям ключей.

![map](./images/map.png)

## Создание экземпляра класса pair

Класс `pair` (пара) стандартной библиотеки С++ позволяет нам определить одним объектом пару значений, если между ними есть какая-либо семантическая связь. Эти значения могут быть одинакового или разного типа. Например, инструкция

```cpp
std::pair<std::string, int> pr("Key", 10);
```

создает объект pr типа `pair`, состоящий из двух значений.

Отдельные части пары могут быть получены с помощью членов `first` и `second`:

```cpp
#include <iostream>

int main() {
  std::pair<std::string, int> pr("Key", 10);
  std::cout << "pr: " << pr.first << ' ' << pr.second << std::endl;
}
```

Получим в результате:

```bash
pr: Key 10
```

Итак, map содержит пары (объекты класса-шаблона `pair`), каждая пара состоит из ключа (`first`) и значения (`second`), ассоциированного с ключом.

## Создание экземпляра класса map

Создать экземпляра класса map можно следующими способами:

1. объявить экземпляр класса map без инициализации. Для этого перед названием переменной указывается название класса. После названия переменной внутри угловых скобок через запятую задаются типы данных ключа и значения. В этом случае объект не содержит элементов. Пример объявления без инициализации:

   ```cpp
   std::map<std::string, int> m;
   ```

2. указать объект класса map внутри круглых скобок или после оператора `=`:

   ```cpp
   std::map<std::string, int> m1;
   std::map<std::string, int> m2(m1);
   std::map<std::string, int> m3 = m1;
   ```

### Вставка элементов

Вставить элемент можно, указав ключ внутри квадратных скобок. Значение элемента задается после оператора присваивания. Если ключ уже существует, то вместо вставки элемента производится изменение значения. Пример:

```cpp
#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> m;
  std::map<std::string, int>::iterator i;
  m["one"] = 0;  // заполнение в контейнер
  m["two"] = 2;  // заполнение в контейнер
  m["one"] = 1;  // изменение значения по ключу

  for (i = m.begin(); i != m.end(); i++) {
    std::cout << i->first << " -> " << i->second << "; ";
  }
  std::cout << std::endl;
} 
```

Получим в результате:

```bash
one -> 1; two -> 2; 
```

Над двумя объектами класса map определены операции `==`, `!=`, `<`, `<=`, `>` и `>=`. Кроме того, один объект можно присвоить другому объекту. Пример:

```cpp
#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<int, int> m1, m2;
  std::map<int, int>::iterator i;
  m1[0] = 10;  // заполнение контейнера
  m1[1] = 20;  // заполнение контейнера
  m2 = m1;
  for (i = m2.begin(); i != m2.end(); i++) {
    std::cout << i->first << ' ' << i->second << "; ";
  }
  std::cout << std::endl;
}
```

Получим в результате:

```bash
0 10; 1 20; 
```

Обратите внимание, как в примере производится перебор всего содержимого отображения и вывод каждой пары "ключ/значение". Для этого используется итератор `i`:

```cpp
std::map<int, int>::iterator i;
```

разыменование которого дает пару (объект `pair`) с ключом и значением. Доступ к компонентам пары осуществляется через переменные `first` и `second`:

```cpp
std::cout << i->first << ' ' << i->second << "; ";
```

Как уже упоминалось, в ассоциативном контейнер можно хранить только уникальные ключи. Дублирования ключей не допускается.

Как правило, для любого объекта, заданного в качестве ключа, должны быть определены конструктор по умолчанию и несколько операторов сравнения.

### Удаление элементов

Для удаления элементов из отображения предназначены следующие методы:

1. `erase()` - удаляет один элемент или элементы из диапазона.

   Пример удаления элемента с указанным ключом:

   ```cpp
   std::map<std::string, int> m;
   std::map<std::string, int>::iterator i;
   m["one"] = 1;
   m["two"] = 2;
   m.erase("one");
   for (i = m.begin(); i != m.end(); ++i) {
     std::cout << i->first << " -> " << i->second << "; ";
   }  // two -> 2;
   ```

   Пример удаления элемента, на который указывает итератор:

   ```cpp
   std::map<std::string, int> m;
   std::map<std::string, int>::iterator i;
   m["one"] = 1;  // заполнение в контейнер
   m["two"] = 2;
   m.erase(--m.end());
   for (i = m.begin(); i != m.end(); i++) {
     std::cout << i->first << " -> " << i->second << "; ";
   }  // one -> 1;
   ```

2. `clear()` – удаление всех элементов.
3. `empty()` – возвращает значение true, если контейнер не содержит элементов, и `false` – в противном случае.
4. `size()` – возвращает количество элементов в контейнере. Пример:

   ```cpp
   std::map<std::string, int> m;
   std::map<std::string, int>::iterator i;
   m["one"] = 1;
   m["two"] = 2;
   m["third"] = 3;
   m["four"] = 4;
   
   std::cout << "size: " << m.size() << std::endl;  // 4
   m.clear();
   if (m.empty()) {
     std::cout << "Нет элементов\n";  // Нет элементов
   }
   std::cout << "size: " << m.size() << std::endl;  // 0
   ```

### Доступ к элементам

К любому  элементу можно обратиться как к элементу массива. Достаточно указать его ключ внутри квадратных скобок. Можно как получить значение, так и изменить его. Если производится присваивание значения по ключу и ключа не существует, то производится вставка элемента, если элемент уже существует, то его значение изменяется на новое. Если производится получение значения по ключу и ключа не существует, то элемент вставляется со значением по умолчанию для типа, а затем это значение возвращается.

Пример:

```cpp
std::map<std::string, int> m;
std::map<std::string, int>::iterator i;
m["one"] = 1;  // Вставляем новый элемент
m["two"] = 2;
m["one"] = 100;  // Изменяем значение существующего элемента
std::cout << m["one"] << std::endl;  // 100
std::cout << m["two"] << std::endl;  // 2
std::cout << m["key"] << std::endl;  // 0 (элемент вставлен)

for (i = m.begin(); i != m.end(); ++i) {
std::cout << i->first << " -> " << i->second << "; ";
}  // key -> 0; one -> 100; two -> 2;
```

Для доступа к элементам предназначены следующие методы:

1. `count(Keyval)` – возвращает количество элементов, у которых ключ соответствует значению `Keyval`.
2. `find(Keyval)` – возвращает итератор, установленный на элемент, ключ которого соответствует значению `Keyval`. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента.

#### Пример 1

В следующей программе на примере ассоциативного контейнера, предназначенного для хранения десяти пар ключ/значение, иллюстрируются основы использования ассоциативных контейнеров. Ключом здесь является символ, а значением — целое. Пары ключ/значение хранятся следующим образом:

```bash
A   0
B   1
C   2
. . .
J   9
```

Поскольку пары хранятся именно таким образом, то, когда пользователь набирает на клавиатуре ключ (т. е. одну из букв от `А` до `J`), программа выводит на экран соответствующее этому ключу значение.

```cpp
#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<char, int> m;
  int i;
  // размещение пар в ассоциативном списке
  for (i = 0; i < 10; i++) {
    m['A' + i] = i;
  }
  char ch;
  std::cout << "Введите ключ: ";
  std::cin >> ch;
  std::map<char, int>::iterator p;
  // поиск значения по заданному ключу
  p = m.find(ch);
  if (p != m.end()) {
    std::cout << p->second;
  } else {
    std::cout << "Такого ключа в ассоциативном списке нет";
  }

  std::cout << std::endl;
}
```

Получим в результате:

```bash
Введите ключ: B
1
```

После того как ассоциативный контейнер инициализирован парами ключ/значение, найти нужное значение по заданному ключу можно с помощью функции `find()`. Функция `find()` возвращает итератор соответствующего ключу элемента или итератор конца ассоциативного контейнера, если указанный ключ не найден. Когда соответствующее ключу значение найдено, оно выводится в консоль.

#### Пример 2

Так же как и в других контейнерах, в ассоциативных контейнерах можно хранить создаваемые вами типы данных. Например, в представленной ниже программе создается отображение для хранения слов с соответствующими словам антонимами. С этой целью используются два класса: `word` (слово) и `opposite` (антоним). Поскольку для ассоциативных контейнеров поддерживается отсортированный список ключей, в программе для объектов типа word определяется оператор `<`. Как правило, оператор `<` необходимо перегружать для всех классов, объекты которых предполагается использовать в качестве ключей. (Помимо оператора `<` в некоторых компиляторах может потребоваться определить дополнительные операторы сравнения).

```cpp
#include <iostream>
#include <map>

class word {
  char str[20];

 public:
  word() { strcpy(str, ""); }

  word(char* s) { strcpy(str, s); }

  word(const char* s) { strcpy(str, s); }

  char* get() { return str; }

  // Для объектов типа word следует определить оператор < (меньше)
  bool operator<(word b) { return strcmp(get(), b.get()) < 0; }
};

// Для объектов типа word следует определить оператор < (меньше)
bool operator<(word a, word b) { return strcmp(a.get(), b.get()) < 0; }

class opposite {
  char str[20];

 public:
  opposite() { strcpy(str, ""); }

  opposite(const char* s) { strcpy(str, s); }

  char* get() { return str; }
};

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<word, opposite> m;
  // Размещение в ассоциативном контейнере имен абонентов
  // и их телефонных номеров
  m[word("Vasiliy")] = opposite("541-85-51");
  m[word("Joseph")] = opposite("550-09-96");
  m[word("Michael")] = opposite("8-3712-41-16-36");
  m[word("Nicodem")] = opposite("8-095-967-85-85");
  // Поиск телефонного номера по заданному имени абонента
  char str[80];
  std::cout << "Введите имя: ";
  std::cin >> str;
  std::map<word, opposite>::iterator p;
  p = m.find(word(str));
  if (p != m.end()) {
    std::cout << "Телефонный номер: " << p->second.get();
  } else {
    std::cout << "Такого имени в ассоциативном контейнере нет";
  }
  std::cout << std::endl;
}
```

Получим в результате:

```bash
Введите имя: Michael
Телефонный номер: 8-3712-41-16-36
```

В данном примере любой объект, который вводится в ассоциативный контейнер, представляет собой символьный массив для хранения заканчивающейся нулем строки.

#### Пример 3

Поскольку класс `string` определяет тип данных, появляется возможность создавать контейнеры для хранения объектов типа `string`. Например, ниже представлена усовершенствованная версия программы создания ассоциативного списка для хранения слов и антонимов.

```cpp
#include <iostream>
#include <map>

int main() {
#ifdef WIN32
  system("chcp 65001");
#else
  setlocale(LC_ALL, "Russian");
#endif
  std::map<std::string, std::string> m;
  m["yes"] = "no";
  m["well"] = "no";
  m["left"] = "right";
  m["up"] = "down";
  std::string s;
  std::cout << "Введите слово: ";
  std::cin >> s;
  std::map<std::string, std::string>::iterator p;
  p = m.find(s);
  if (p != m.end()) {
    std::cout << "Антоним: " << p->second;
  } else {
    std::cout << "Такого слова в ассоциативном списке нет";
  }
  std::cout << std::endl;
}
```

Получим в результате:

```bash
Введите слово: yes
Антоним: no
```
